package algorithm.leetcode.I101to200;

import algorithm.leetcode.TreeNode;

public class Q110 {
    public boolean isBalanced(TreeNode root) {
        return root == null ||
                (isBalanced(root.right) && isBalanced(root.left) && Math.abs(height(root.left) - height(root.right)) <= 1);

    }

    public static int height(TreeNode node) {
        return node == null ? 0 : Math.max(height(node.left), height(node.right)) + 1;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(4), b = new TreeNode(4), c = new TreeNode(3), d = new TreeNode(3), e = new TreeNode(2),
                f = new TreeNode(2), g = new TreeNode(1);
        g.left = e;
        g.right = f;
        e.left = c;
        e.right = d;
        c.left = a;
        c.right = b;
        Q110 solution = new Q110();
        System.out.println(solution.isBalanced(g));

    }
}

